#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define VAZIO "[---]"
#define NULO "  -1"
typedef struct
{
    char head[5];
    char first_aval[5];
} Header;

typedef struct
{
    char offsets[4][5];
    char keys[3][6];
} Pagina;

typedef struct
{
    char key[6];
    char next_offset[5];
} Promote;

void initBTree(const char *arq_name);
void insertItemBTree(FILE *f, char key[6]);
void createRootPage(FILE *f, Promote p, int minor_offset);
void getHeader(FILE **f, Header *h);
void putHeader(FILE *f, Header h);
void getPage(FILE *f, Pagina *p, int offset);
void putPage(FILE *f, Pagina p, int offset);
Promote fun(FILE *f, int offset, char key[5]);
Promote insertItemPage(FILE *f, Pagina *p, int offset, Promote *Item);
int searchItemBTree(FILE *f, char key[6]);
void removeItemBTree(FILE *f, char key[6]);
int createNewPage(FILE *f, Pagina p, int offset);
Promote splitOverflow(FILE *f, Pagina *p1, int offset, char key[5]);

int main(void)
{
    FILE *arq;
    char chave[6];
    
    arq = fopen("index.dat", "rb+");
    gets(chave);
    insertItemBTree(arq, chave);
    
    fclose(arq);
    system("pause");
	
    return 0;
}

void initBTree(const char *arq_name)
{
    FILE *fb;
    char header[26], pagina[31];
    Pagina p;
    strcpy(p.offsets[0], NULO);
    strcpy(p.offsets[1], NULO);
    strcpy(p.offsets[2], NULO);
    strcpy(p.offsets[3], NULO);
    strcpy(p.keys[0], VAZIO);
    strcpy(p.keys[1], VAZIO);
    strcpy(p.keys[2], VAZIO);
    sprintf(pagina, "%s%s%s%s%s%s%s", p.offsets[0], p.keys[0], p.offsets[1], p.keys[1], p.offsets[2], p.keys[2], p.offsets[3]);
    strcpy(header, "HEAD=0026 FIRST_AVAL=  -1\n");
    fb = fopen(arq_name, "wb");
    fwrite(header, sizeof(char), 26, fb);
    fwrite(pagina, sizeof(char), 31, fb);
    fclose(fb);
    
}

void insertItemBTree(FILE *f, char key[6])
{
    Header h;
    int offset;
    Promote p;
    
    getHeader(&f, &h);
    
    sscanf(h.head, "%d", &offset);
    p = fun(f, offset, key);
    if( strcmp(p.key, VAZIO) )
        createRootPage(f, p, offset);
    
}

void createRootPage(FILE *f, Promote p, int minor_offset)
{
    Header h;
    Pagina root;
    int first_aval, new_head;
    
    getHeader(&f, &h);
    sscanf(h.first_aval, "%d", &first_aval);
    sprintf(root.offsets[0], "%04d", minor_offset);
    strcpy(root.offsets[1], p.next_offset);
    strcpy(root.offsets[2], NULO);
    strcpy(root.offsets[3], NULO);
    strcpy(root.keys[0], p.key);
    strcpy(root.keys[1], VAZIO);
    strcpy(root.keys[2], VAZIO);
    new_head = createNewPage(f, root, first_aval);
    sprintf(h.head, "%04d", new_head);
    putHeader(f, h);
    
}

void getHeader(FILE **f, Header *h)
{
    char header[27];
    int i;
    
    fseek(*f, 0, SEEK_SET);
    
	if(fread(header, sizeof(char), 26, *f) == 0)
    {
        fclose(*f);
        initBTree("index.dat");
        *f = fopen("index.dat", "rb+");
        fread(header, sizeof(char), 26, *f);
    }
    
	header[26] = '\0';
	
    for(i=5; i < 9; i++)
        h->head[i-5] = header[i];
		
    for(i=21; i < 25; i++)
        h->first_aval[i-21] = header[i];
    
}

void putHeader(FILE *f, Header h)
{
    char header[27];
    sprintf(header, "HEAD=%s FIRST_AVAL=%s\n", h.head, h.first_aval);
    fseek(f, 0, SEEK_SET);
    fwrite(header, sizeof(char), 26, f);
}

void getPage(FILE *f, Pagina *p, int offset)
{
    char pagina[31];
    int i;
    
    fseek(f, offset, SEEK_SET);
    fread(pagina, sizeof(char), 31, f);
    
    for(i=0; i < 4; i++)
        p->offsets[0][i] = pagina[i];
    p->offsets[0][4] = '\0';
    
    for(; i < 9; i++)
        p->keys[0][i-4] = pagina[i];
    p->keys[0][5] = '\0';
    
    for(; i < 13; i++)
        p->offsets[1][i-9] = pagina[i];
    p->offsets[1][4] = '\0';
    
    for(; i < 18; i++)
        p->keys[1][i-13] = pagina[i];
    p->keys[1][5] = '\0';
    
    for(; i < 22; i++)
        p->offsets[2][i-18] = pagina[i];
    p->offsets[2][4] = '\0';
    
    for(; i < 27; i++)
        p->keys[2][i-22] = pagina[i];
    p->keys[2][5] = '\0';
    
    for(; i < 31; i++)
        p->offsets[3][i-27] = pagina[i];
    p->offsets[3][4] = '\0';

}

void putPage(FILE *f, Pagina p, int offset)
{
    char pagina[32];
    
    sprintf(pagina, "%s%s%s%s%s%s%s", p.offsets[0], p.keys[0], p.offsets[1], p.keys[1], p.offsets[2], p.keys[2], p.offsets[3]);
    fseek(f, offset, SEEK_SET);
    fwrite(pagina, sizeof(char), 31, f);
    
}

Promote fun(FILE *f, int offset, char key[5])
{
    char chave[5];
    int new_offset;
    Pagina p;
    Promote sobe;
    
    strcpy(sobe.key, key);
    strcpy(sobe.next_offset, NULO);
    
    getPage(f, &p, offset);
    
    if( strcmp(p.offsets[0], NULO) )
    {
        if( strcmp(key, p.keys[0]) < 0)
        {
            sscanf(p.offsets[0], "%d", &new_offset);
            sobe = fun(f, new_offset, key);
            strcpy(chave, sobe.key);
        }
        else if( strcmp(key, p.keys[1]) < 0)
        {
            sscanf(p.offsets[1], "%d", &new_offset);
            sobe = fun(f, new_offset, key);
            strcpy(chave, sobe.key);
        }
        else if( strcmp(key, p.keys[2]) < 0)
        {
            sscanf(p.offsets[2], "%d", &new_offset);
            sobe = fun(f, new_offset, key);
            strcpy(chave, sobe.key);
        }
        else
        {
            sscanf(p.offsets[3], "%d", &new_offset);
            sobe = fun(f, new_offset, key);
            strcpy(chave, sobe.key);
        }
    }
    else
        return insertItemPage(f, &p, offset, &sobe);
    
    if( strcmp(chave, VAZIO) )
        return insertItemPage(f, &p, offset, &sobe);
    
    strcpy(sobe.key, VAZIO);
    
	return sobe;
}

Promote insertItemPage(FILE *f, Pagina *p, int offset, Promote *Item)
{
    Promote aux, pos;
    int i;
    
    strcpy(pos.key, VAZIO);
	
    for(i=0; i < 3; i++)
    {
        if( strcmp(p->keys[i], VAZIO) )
        {
            if( strcmp(Item->key, p->keys[i]) < 0)
            {
                strcpy(pos.key, p->keys[i]);
                strcpy(pos.next_offset, p->offsets[i+1]);
                strcpy(p->keys[i], Item->key);
                strcpy(p->offsets[i+1], Item->next_offset);
				
                break;
            }
        }
        else
        {
            strcpy(p->keys[i], Item->key);
            strcpy(p->offsets[i+1], Item->next_offset);
            i = 5;
			
            break;
        }
    }

    for(i++; i < 3; i++)
    {
        strcpy(aux.key, p->keys[i]);
        strcpy(aux.next_offset, p->offsets[i+1]);
        strcpy(p->keys[i], pos.key);
        strcpy(p->offsets[i+1], pos.next_offset);
        
		if( !strcmp(aux.key, VAZIO) )
            break;
        
		pos = aux;
    }
    
    if(i == 3)
    {
        return splitOverflow(f, p, offset, pos.key);
    }
    else if(i == 4)
    {
        return splitOverflow(f, p, offset, Item->key);
    }

    
    putPage(f, *p, offset);
    strcpy(aux.key, VAZIO);
    return aux;

}

Promote splitOverflow(FILE *f, Pagina *p1, int offset, char key[5])
{
    Promote sobe;
    Pagina p2;
    Header h;
    int offset_newpage, first_aval;
    
    strcpy(p2.offsets[0], NULO);
    strcpy(p2.offsets[1], NULO);
    strcpy(p2.offsets[2], NULO);
    strcpy(p2.offsets[3], NULO);
    strcpy(p2.keys[0], key);
    strcpy(p2.keys[1], VAZIO);
    strcpy(p2.keys[2], VAZIO);
	
    getHeader(&f, &h);
    sscanf(h.first_aval, "%d", &first_aval);
    offset_newpage = createNewPage(f, p2, first_aval);
    strcpy(sobe.key, p1->keys[2]);
    strcpy(p1->keys[2], VAZIO);
    putPage(f, *p1, offset);
    sprintf(sobe.next_offset, "%04d", offset_newpage);
    
    return sobe;
}

int createNewPage(FILE *f, Pagina p, int offset)
{
    if(offset != -1)
        putPage(f, p, offset);
    else
    {
        fseek(f, 0, SEEK_END);
        offset = ftell(f);
        putPage(f, p, offset);
    }
    return offset;
}
